#include "tree.hpp"
#include <algorithm>
/*===========================================================================*/
/* KLASA cNode*/
/*===========================================================================*/

cNode::cNode(unsigned char initial_znak, int initial_waga, int initial_licznik, cNode *rodzic){
            znak = initial_znak;
            waga  = initial_waga;
            licznik = initial_licznik;
            Left=NULL;
            Right=NULL;
            Parent = rodzic;
}

/*===========================================================================*/
/* KLASA cTree*/
/*===========================================================================*/

cTree::cTree(int rozmiar){
    this->iRozmiar_alfabetu = rozmiar;

    head=new cNode(NULL, 0, iRozmiar_alfabetu--, NULL);
    nyt = head;
}

inline bool cTree::bIs_nyt(cNode *wsk){
    if(wsk)
        if(wsk == nyt)
            return 1;
    return 0;
}

inline bool cTree::bIs_znak(cNode *wsk){
    if(wsk)
        if(wsk->Left == NULL && wsk->Right == NULL && wsk!= nyt)
            return 1;
    return 0;
}

inline bool cTree::bIs_rodzic(cNode *wsk){
    if(wsk)
        if(wsk->Left != NULL && wsk->Right != NULL && wsk->waga != 0 )
            return 1;
    return 0;
}
void cTree::vAdd_new_node(unsigned char znak, cNode *wierzcholek)    //dodaje wierzcholek do drzewa
{
    wierzcholek=Search_znak(head, znak);

    if(!wierzcholek)    // pierwsze wystapienie znaku
    {
        wierzcholek = nyt;

        wierzcholek->Right = new cNode(znak, 1, iRozmiar_alfabetu--, wierzcholek);
        wierzcholek->Left = new cNode(NULL, 0, iRozmiar_alfabetu--, wierzcholek);

        nyt = wierzcholek->Left;

        wierzcholek->waga++;
        wierzcholek= nyt->Parent;
    }
    else{  //znak juz wystpił

        cNode *najwiekszy;
        int licz =0;

        vSearch_biggest_in_block(head, wierzcholek, najwiekszy, licz);
        if(najwiekszy->licznik > wierzcholek->licznik){
            vSwap_nodes(wierzcholek, najwiekszy);
        }
        wierzcholek->waga++;

    }

    while(wierzcholek != head){
        cNode *najwiekszy;
        int licz =0;

        wierzcholek= wierzcholek->Parent;// przechodze do wierzcholka Rodzica
        vSearch_biggest_in_block(head, wierzcholek, najwiekszy, licz);
        if(najwiekszy->licznik > wierzcholek->licznik){
            vSwap_nodes(wierzcholek, najwiekszy);
        }
        wierzcholek->waga++;

    }
    }

cNode *cTree::Search_znak(cNode *aktualny, unsigned char znak)
{
    cNode *left, *right, *wsk;
    if  (aktualny->znak == znak
            && bIs_znak(aktualny)
            && aktualny->waga!=0){

        return aktualny;
    }else{

        left = aktualny->Left;
        right = aktualny->Right;
        if(right){
        wsk = Search_znak(right, znak);
        if(wsk) return wsk;

        if(left){
        wsk = Search_znak(left, znak);
        if(wsk) return wsk;
        }

        }
    }
    return NULL;
}


void cTree::vSearch_biggest_in_block(cNode *aktualny, cNode *szukany, cNode *&najwiekszy, int &licznik){
    cNode *left, *right;

    if(aktualny->waga == szukany->waga && aktualny->licznik > licznik && aktualny != szukany->Parent){
        licznik = aktualny->licznik;
        najwiekszy = aktualny;

    }
    if(aktualny->Left){
    left = aktualny->Left;

    vSearch_biggest_in_block(left, szukany, najwiekszy, licznik);
    }

    if(aktualny->Right){
    right = aktualny->Right;
    vSearch_biggest_in_block(right, szukany, najwiekszy, licznik);
    }
}

void cTree::vSwap_nodes(cNode *a, cNode *b)
{
    cNode *temp1, *temp2;
    int temp_int = a->licznik;
    temp1 = a->Parent;
    temp2 = b->Parent;

    if(temp1->Right == a)
        temp1->Right = b;
    else if(temp1->Left == a)
        temp1->Left = b;
    b->Parent = temp1;

    if(temp2->Right == b)
        temp2->Right = a;
    else if(temp2->Left == b)
        temp2->Left = a;
    a->Parent = temp2;

    a->licznik = b->licznik;
    b->licznik = temp_int;

}

string cTree::sNyt_path(cNode *wsk, string &path)
{

if(bIs_rodzic(wsk)){
    if(bIs_nyt(wsk->Left)){
        path+="0";
        return path;
    }
    if(bIs_nyt(wsk->Right)){
        path+="1";
        return path;
    }
    if(bIs_rodzic(wsk->Left)){
        path+="0";
        return sNyt_path(wsk->Left, path);
    }
    if(bIs_rodzic(wsk->Right)){
        path+="1";
        return sNyt_path(wsk->Right, path);
    }
}
    return path;
}

void cTree::vPath(cNode *aktualny, string &path)
{
    //if (aktualny->znak==NULL)   cout <<"ide do nula \n";
    cNode *poprzedni;

    poprzedni = aktualny;
    while(aktualny == aktualny->Parent){

    if(aktualny->Left == poprzedni)
        path+="0";

    if(aktualny->Right == poprzedni)
        path+="1";
    poprzedni = aktualny;
    }

    reverse(path.begin(), path.end());
    //cout <<path<<endl;
}
